⟸ Go Back ⟸

Exercise 6 (Homework 1).

(homomorphism, theory of languages)

Homomorphisms I – basic properties

Let \sigma :\Sigma^* \to \Sigma^* be a function. Which of the following definitions of \sigma define a homomorphism? That is, which ones satisfy that for any words x,y\in \Sigma^*, \sigma(xy)=\sigma(x)\sigma(y)? Let w=a_1a_2\cdots a_n \in \Sigma^*, where a_1,a_2,\dots, a_n \in \Sigma.

1. \sigma(w)=a_1a_1a_2a_2\cdots a_na_n.
2. \sigma(w)=a_1a_2a_2a_3a_3a_3\cdots\overbrace{a_n\cdots a_n}^{n)}.
3. \sigma(w)=ww.
4. \sigma(w)=w.
5. \sigma(w)=\lambda.
6. \sigma(w)=a^{|w|}, where a\in \Sigma.
7. \sigma(w)=w^R.
8. \sigma(w)=\sigma_1(\sigma_2(w)), where \sigma_1,\sigma_2 are homomorphisms.